Many technical problems involve hypergraph partitioning.
In fact, graphs and hypergraphs are mathematical objects that are useful for representing data obtained in various scientific or industrial applications.
More precisely, graphs and hypergraphs describe a collection of nodes, or vertices, connected together through edges. The data relevant to the specific problem can be attached to vertices, and/or edges which are referred to as the vertex and edge metadata. It will be appreciated that part of the problem-specific information may be also stored in the structure of the hypergraph itself by specifying the vertices and the edges between them.
It will be appreciated that a graph is defined as an ordered pair G=(V, E) comprising a set V of vertices and a set E of edges which are 2-subsets of V.
A hypergraph is defined as an ordered pair G=(V, E) comprising a set V of vertices and a set E of edges which are subsets of V.
The weight of an edge may be defined to be equal to a function of a plurality of edge and vertex properties. In one embodiment, the weight does not depend on other properties and a unit weight is simply assigned to all edges of the input hypergraph.
The vertex weight can be defined to be another vertex property of the hypergraph or a function of a plurality of the vertex and edge properties. In one embodiment, the vertex property is a unit weight.
It will be appreciated that the goal of performing a graph partitioning is to divide the vertex set V of a graph G into a given number of disjoint parts of approximately the same weight so that a metric on the number and weight of inter-partition edges is minimized.
It will be further appreciated that the size of a hypergraph or a partition is defined as the number of vertices in the hypergraph or partition. It will be appreciated that the weight of a hypergraph or partition can be defined as the sum of the vertex weights in the hypergraph or partition. In one embodiment where the vertex weight is initialized to be a unit weight, the two definitions coincide.
When partitioning a hypergraph, edges are cut by the lines dividing the partitions. It will be appreciated that the edge of a hypergraph is not cut if all vertices attached to it are in one partition, and cut exactly once otherwise, no matter how many vertices are assigned to each partition.
Various generalizations of graph partitioning exist, having been adapted for specific technical problems by imposing additional constraints on the individual partitions.
The skilled addressee will appreciate that graph partitioning falls under the category of NP-hard problems. Solutions are generally derived using heuristic or approximation algorithms. Furthermore, even approximating the balanced graph partitioning can be shown to be NP-complete.
It will be appreciated that the solving of a problem involving a hypergraph partitioning is therefore cumbersome since it requires large amount of resources.
Another issue is that most interesting applications involving hypergraph partitioning involve very large graphs for which exact methods are prohibitively slow.
Another issue with the solving of a problem involving a hypergraph is that faster methods come at the cost of sacrificing the quality of the solution by introducing multiple approximations.
There is a need for a method and system that will overcome at least one of the above-identified drawbacks.
Features of the invention will be apparent from review of the disclosure, drawings and description of the invention below.